package cn.edu.xjtu.work.getMaxDoller;

/**
 * @author Hydrion-QLz
 * @date 2022-09-17 21:07
 * @description 分奖金问题
 * 给定一个数组，数组中的每一个值为一份奖金，可以将一份奖金分为任意份，给定员工数目为k，每个员工奖金相同且只能拿一份奖金
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5};
        System.out.println(getMaxDoller(arr, 4));
    }

    private static int getMaxDoller(int[] arr, int k) {
        int left = 1;
        int right = 0;
        for (int val : arr) {
            right = Math.max(right, val);
        }

        while (left <= right) {
            int center = left + (right - left) / 2;
            if (check(arr, center, k)) {
                left = center + 1;
            } else {
                right = center - 1;
            }
        }
        return right;
    }

    private static boolean check(int[] arr, int doller, int k) {
        for (int val : arr) {
            k -= val / doller;
        }
        return k <= 0;
    }
}
